package greedy_algorithm;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//class point {
//	double x;
//	double y;
//	point(double x,double y){
//		this.x=x;
//		this.y=y;
//	}
//	public String toString(){
//		String str="("+this.x+","+this.y+")";
//		return str;
//	}
//}

public class violence {
    
    public static Stack<point> stack = new Stack<point>();
    static double min_distance=Integer.MAX_VALUE;
    public static void main(String[] args) {
        //int shu[] = {1,2,3,4,5,6,7,8,9,10};
        point a1=new point(569,738);
		point a2=new point(231,433);
		point a3=new point(345,987);
		point a4=new point(564,897);
		point a5=new point(134,897);
		point a6=new point(908,234);
		point a7=new point(687,343);
		point a8=new point(569,246);
		point a9=new point(679,146);
		point a0=new point(681,874);
		List<point> in=new ArrayList<point>();
		in.add(a1);in.add(a0);in.add(a9);in.add(a8);in.add(a7);in.add(a6);in.add(a5);in.add(a4);in.add(a3);in.add(a2);
        //f(shu,10,0);
		TSP(in,in.size(),0);
		System.out.println(min_distance);
    }
    /**
     *
     * @param shu   待选择的数组
     * @param targ  要选择多少个次
     * @param cur   当前选择的是第几次
     */
//    private static void f(int[] shu, int targ, int cur) {
//        // TODO Auto-generated method stub
//        if(cur == targ) {
//            System.out.println(stack);
//            return;
//        }
//         
//        for(int i=0;i<shu.length;i++) {
//            if(!stack.contains(shu[i])) {
//                stack.add(shu[i]);
//                f(shu, targ, cur+1);
//                stack.pop();
//            }
//        }
//    }
    public static void TSP(List<point> in,int targ,int cur) {
    	if(cur==targ) {
    		List<point> temp=new ArrayList<point>();
    		//System.out.println(stack);
    		for(int i=0;i<stack.size();i++) {
    			temp.add(stack.get(i));
    		}
    		double s=dist(temp);
    		if(min_distance>s) {
    			min_distance=s;
    		}
            return;
    	}
    	for(int i=0;i<in.size();i++) {
    		if(!stack.contains(in.get(i))) {
    			stack.add(in.get(i));
    			TSP(in,targ,cur+1);
    			stack.pop();
    		}
    	}
    }
    //用来计算整个数组中的点的距离之和如p1->p2->p3->p1所用的距离
    public static double dist(List<point> in) { 
    	double di=0;
    	for(int i=0;i<in.size()-1;i++) {
    		di=di+Math.sqrt(Math.pow((in.get(i+1).x-in.get(i).x), 2)+Math.pow((in.get(i+1).y-in.get(i).y), 2));
    	}
    	di=di+Math.sqrt(Math.pow((in.get(in.size()-1).x-in.get(0).x), 2)+Math.pow((in.get(in.size()-1).y-in.get(0).y), 2));
    	//System.out.println(di);
    	return di;
    }
}